/**
 * 
 */
package com.module.hq.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

import com.dalonedrau.graph.GraphEdge;
import com.dalonedrau.graph.SparseGraph;
import com.dalonedrau.graph.UninformedGraphDepthSearch;

/**
 * @author Donald
 */
public class HQGraphSearchBreadthFirst {
	private static final int	NO_PARENT_ASSIGNED	= -3;
	private static final int	UNVISITED			= -2;
	private static final int	VISITED				= -1;
	/** flag indicating that the target has been found. */
	private boolean				found;
	/** the graph being searched. */
	private HQCellGraph			graph;
	/** the route to the target. */
	private int[]				route;
	/** the source node from where the search originates. */
	private int					source;
	/** the target node from where the search ends. */
	private int					target;
	/** the vector of all nodes visited as part of the search. */
	private int[]				visited;
	/**
	 * Creates a new instance of {@link HQGraphSearchBreadthFirst}.
	 * @param graph
	 */
	public HQGraphSearchBreadthFirst(final HQCellGraph g) {
		graph = g;
		source = -1;
		target = -1;
		found = false;
		visited = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < visited.length; i++) {
			visited[i] = HQGraphSearchBreadthFirst.UNVISITED;
		}
		route = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < route.length; i++) {
			route[i] = HQGraphSearchBreadthFirst.NO_PARENT_ASSIGNED;
		}
	}
	public void clear() {
		source = -1;
		target = -1;
		found = false;
		for (int i = 0; i < visited.length; i++) {
			visited[i] = HQGraphSearchBreadthFirst.UNVISITED;
		}
		for (int i = 0; i < route.length; i++) {
			route[i] = HQGraphSearchBreadthFirst.NO_PARENT_ASSIGNED;
		}
	}
	/**
	 * Gets the graph
	 * @return {@link SparseGraph}
	 */
	public HQCellGraph getGraph() {
		return graph;
	}
	public Integer[] getPathToTarget() {
		ArrayList<Integer> path = new ArrayList<Integer>();
		// just return an empty path if no path to target found or if
		// no target has been specified
		// if there is no path to the target, or no target was specified,
		// an empty path is returned. otherwise, the path is filled below
		if (found && target >= HQCellGraph.INVALID_NODE_INDEX) {
			int node = target;
			path.add(node);
			while (node != source) {
				node = route[node];
				path.add(0, node);
			}
		}
		return path.toArray(new Integer[path.size()]);
	}
	/**
	 * Determines if the target node has been found.
	 * @return true if the target node has been found; false otherwise
	 */
	public boolean isFound() {
		return found;
	}
	public void search(final int src, final int targ) throws Exception {
		source = src;
		target = targ;
		for (int i = 0; i < visited.length; i++) {
			visited[i] = HQGraphSearchBreadthFirst.UNVISITED;
		}
		for (int i = 0; i < route.length; i++) {
			route[i] = HQGraphSearchBreadthFirst.NO_PARENT_ASSIGNED;
		}
		found = searchBreadthFirst();
	}
	private boolean searchBreadthFirst() throws Exception {
		// create a queue of edges
		LinkedList<GraphEdge> list = new LinkedList<GraphEdge>();
		// create an initial dummy edge and push it on the queue
		GraphEdge dummy = new GraphEdge(source, source);
		list.offer(dummy);
		// mark the source node as visited
		visited[source] = VISITED;
		// while there are edges in the queue keep searching
		while (!list.isEmpty()) {
			// grab the next edge
			GraphEdge next = list.poll();
			// make a note of the parent of the node this edge points to
			route[next.getTo()] = next.getFrom();
			// test for termination. If the edge's destination node is
			// the target node, then the search can return success
			if (next.getTo() == target) {
				//System.out.println("found target");
				return true;
			}

			// push the edges leading from the node at the end of this edge
			// onto the queue
			GraphEdge[] edges = graph.getEdgesFromNode(next.getTo());
			for (int i = 0; i < edges.length; i++) {
				// if the node hasn't already been visited we can push the
				// edge onto the queue
				if (visited[edges[i].getTo()] == UNVISITED) {
					list.offer(edges[i]);

					// the node is marked as visited here, BEFORE it is
					// examined, because
					// it ensures a maximum of N edges are ever placed in the
					// queue,
					// rather than E edges.
					visited[edges[i].getTo()] = VISITED;
				}
			}
		}
		return false;
	}
}
